import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.LinkedList;

import preSetExceperement.InputTable;

import Blocks.Block;
import Blocks.NextState;
import DataStructures.myTree;
import GUI.TerminalAnswer;

public class TerminalStateIdentification {
	private myTree<Block> terminalTree;
	private InputTable machineStates;
	private int statesNumber;
	private TreeRules rules;
	private ArrayList<Integer> answers;
	private ArrayList<TerminalAnswer> finalAns = new ArrayList<TerminalAnswer>();
/**
 * constructor
 * 
 * @param input
 */
	public TerminalStateIdentification(InputTable input) {
		// TODO Auto-generated constructor stub
		terminalTree = new myTree<Block>();
		machineStates = input;
		statesNumber = input.size();
		rules = new TreeRules();
		answers = new ArrayList<Integer>();
		init();
	}
   /**
    * initialize the tree and its root
    */
	private void init() {
		BitSet startStates = new BitSet();
		for (int i = 0; i < statesNumber; i++) {
			startStates.set(i);
		}
		NextState n = new NextState(startStates);
		LinkedList<NextState> firstLinked = new LinkedList<NextState>();
		firstLinked.add(n);
		Block first = new Block(firstLinked);
		first.setEndBlock(false);
		terminalTree.setRoot(first);
	}

	private String[] getBitSetElements(BitSet givenstates) {
		String bitSetElements = givenstates.toString();
		bitSetElements = bitSetElements.substring(1,
				bitSetElements.length() - 1);
		String[] m = bitSetElements.split(", ");
		return m;
	}

	private Block creatChild(boolean branchChild, Block parent, int index) {
		System.out.println("StartCreatBlcok");
		LinkedList<NextState> parentStates = parent.getNode();
		Block newState = new Block();
		Iterator<NextState> parentIterator = parentStates.iterator();
		while (parentIterator.hasNext()) {
			NextState next = parentIterator.next();
			String parentOut = next.getOutput();
			BitSet states = next.getNextState();
			System.out.println("elements" + states);
			String[] bitSetElements = getBitSetElements(states);
			System.out.println("AllInBlock" + bitSetElements.toString());
			for (int i = 0; i < bitSetElements.length; i++) {
				int tableIndex = Integer.parseInt(bitSetElements[i]);
				int nextState;
				char outPut;

				if (!branchChild) {
					nextState = machineStates.lookUpNextStateZero(tableIndex);
					outPut = machineStates.lookUpOutputZero(tableIndex);

				} else {
					nextState = machineStates.lookUpNextStateOne(tableIndex);
					outPut = machineStates.lookUpOutputOne(tableIndex);
				}
				newState.add(nextState, outPut, parentOut);
			}
		}
		return newState;
	}
/**
 * iterate on the tree
 * if current == null check for all level if all level == null , terminate 
 * check for rule 1 or rule 2
 * else complete the tree
 * 
 */
	private void creatTerminalTree() {
		ArrayList<Block> states = terminalTree.getElements();
		for (int i = 0; i < states.size(); i++) {
			Block currentState = states.get(i);
			// All Tree is Stopped by rule1 or rule2
			
			if (currentState == null) {
				int levelNumber = terminalTree.getLevel(i);
				// next Level all are null
			
				if (terminalTree.isEmptyLevel(levelNumber)) {
					System.out.println("Empty");
					break;
				}
				// some nodes = null
				else {
					terminalTree.insertLeftChild(i, null);
					terminalTree.insertRightChild(i, null);
				}
			} else if (rules.applyRule1(currentState)) {
				terminalTree.insertLeftChild(currentState.getIndex(), null);
				terminalTree.insertRightChild(currentState.getIndex(), null);
				answers.add(currentState.getIndex());
			} else if (rules.applyRule2(currentState, i)) {
				terminalTree.insertLeftChild(currentState.getIndex(), null);
				terminalTree.insertRightChild(currentState.getIndex(), null);
			}
			// complete the tree
			else {
				Block leftChild = creatChild(false, currentState, currentState
						.getIndex());
				terminalTree
						.insertLeftChild(currentState.getIndex(), leftChild);
				Block rightChild = creatChild(true, currentState, currentState
						.getIndex());
				terminalTree.insertRightChild(currentState.getIndex(),
						rightChild);
			}
			rules.init();
		}
	}

	private String getSequence(int index) {
		if (index == -1) {
			return "no sequence";
		}
		StringBuffer sequence = new StringBuffer();
		while (index != 0) {
			if (terminalTree.isLeftChlid(index)) {
				sequence.append(0);
			} else {
				sequence.append(1);
			}
			index = terminalTree.getParent(index);
		}

		sequence = sequence.reverse();
		return sequence.toString();
	}

	public ArrayList<TerminalAnswer> getFinalAns() {
		return finalAns;
	}

	public void setFinalAns(ArrayList<TerminalAnswer> finalAns) {
		this.finalAns = finalAns;
	}

	/**
	 * 
	 * @return String [] contains any path for the tree
	 */
	private String[] anyAnswer() {
		String[] answer = new String[1];
		creatTerminalTree();
		int blockSolutionIndex = answers.get(0);
		System.out.println(getSequence(blockSolutionIndex));
		answer[0] = getSequence(blockSolutionIndex);
		getFinalAns(answer[0], 0);
		return answer;
	}

	private void getFinalAns(String ansI, int index) {
		Block b = new Block();
		b = terminalTree.getElements().get(answers.get(index));
		String[] allNext = new String[b.getNode().size()];
		String[] allOut = new String[b.getNode().size()];
		Iterator<NextState> it = b.getNode().iterator();
		int j = 0;
		while (it.hasNext()) {
			NextState n = it.next();
			int next = Integer.parseInt(n.getNextState().toString().substring(
					1, 2));
			allNext[j] = machineStates.getString(next);
			allOut[j] = n.getOutput();
			j++;
		}
		TerminalAnswer ans = new TerminalAnswer(ansI, allNext, allOut);
		finalAns.add(ans);
	}
/**
 * 
 * @return String[]contains all paths for the tree
 */
	private String[] allAnswers() {

		creatTerminalTree();
		String[] answer = new String[answers.size()];
		for (int i = 0; i < answers.size(); i++) {

			answer[i] = getSequence(answers.get(i));
			getFinalAns(answer[i], i);

		}
		return answer;
	}

	private String[] shortestPath() {

		creatTerminalTree();
		String[] answer = new String[answers.size()];
		int firstLevel = terminalTree.getLevel(answers.get(0));
		answer[0] = getSequence(answers.get(0));
		getFinalAns(answer[0], 0);
		for (int i = 1; i < answers.size(); i++) {
			int currentLevel = terminalTree.getLevel(answers.get(i));
			if (currentLevel == firstLevel) {
				answer[i] = getSequence(answers.get(i));
				getFinalAns(answer[i], i);
			} else {
				break;
			}
		}
		return answer;
	}

	public String[] requiredAnswer(byte required) {
		switch (required) {
		case 1:
			return anyAnswer();
		case 0:
			return allAnswers();
		case -1:
			return shortestPath();
		default:
			return anyAnswer();
		}
	}

	public static void main(String[] args) {

		String[][] m = { { "a", "b", "c", "d" }, { "b", "a", "d", "d" },
				{ "0", "0", "1", "1" }, { "d", "b", "a", "c" },
				{ "0", "0", "0", "0" } };
		InputTable x = new InputTable(m);
		TerminalStateIdentification k = new TerminalStateIdentification(x);
		String[] ans = k.requiredAnswer((byte) 0);
		for (int i = 0; i < ans.length; i++) {
			System.out.println(ans[i]);
		}

	}
}
